package leetcode101.tree;

/**
 * @author Synhard
 * @version 1.0
 * @class Code4
 * @description 437. 路径总和 III
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 *
 * 找出路径和等于给定数值的路径总数。
 *
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 *
 * 示例：
 *
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 *
 *       10
 *      /  \
 *     5   -3
 *    / \    \
 *   3   2   11
 *  / \   \
 * 3  -2   1
 *
 * 返回 3。和等于 8 的路径有:
 *
 * 1.  5 -> 3
 * 2.  5 -> 2 -> 1
 * 3.  -3 -> 11
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-22 8:07
 */
public class Code4 {





    public static void main(String[] args) {

    }

    static int count;

    public static int pathSum(TreeNode root, int targetSum) {
        count = 0;
        if (root == null) {
            return 0;
        }
        getSum(root, 0, targetSum);
        return count + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private static void getSum(TreeNode root, int curVal, int targetSum) {
        if (root == null) {
            return;
        }
        int curSum = curVal + root.val;
        if (curSum == targetSum) {
            count++;
        }
        getSum(root.left, curSum, targetSum);
        getSum(root.right, curSum, targetSum);
    }

}

/*
静态变量count记录了从每一个根节点出发到其所有子节点中路径值等于目标值的个数
pathSum 返回了所有等于目标值的路径条目数
getSum 返回了从指定根节点出发，到达子节点的路径值等于目标值的个数
 */
